\chapter{扩展阅读}
\section{姚期智——图灵奖的介绍}
姚期智教授获得2000年图灵奖，在美国计算机协会ACM的图灵奖获得者介绍中，我们可以看到姚先生的主要贡献，下面摘录在下面。
\par
\vspace{1cm}
In recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity.\par
\vspace{1cm}
Andrew Chi-Chih Yao was born in Shanghai, China, on December 24, 1946. After moving with his family to Hong Kong for two years he immigrated to Taiwan. In 1967 he received a B.S. in Physics from the National University of Taiwan. He then started graduate studies in Physics at Harvard University, where he received an A.M. in 1969 and a Ph.D. in 1972 under the supervision of Sheldon Glashow, winner of the 1979 Nobel Prize in Physics. He subsequently entered the Ph.D. program in Computer Science at the University of Illinois Urbana-Champaign, and received his degree just two years later, in 1975. Yao completed his dissertation, A Study of Concrete Computational Complexity, under the supervision of Chung Laung Liu.
\par
After a year as an Assistant Professor in the Mathematics Department at MIT, Yao joined the Computer Science Department at Stanford University as an Assistant Professor in 1976. Over the next five years there he made a number of fundamental contributions to the theory of algorithms.
\par
His 1977 paper “Probabilistic computations: toward a unified measure of complexity,” [1] introduced what is now known as Yao’s min-max principle, which uses von Neumann’s minimax theorem from game theory to relate average-case complexity for deterministic algorithms to worst-case complexity for randomized algorithms. Yao proved that the expected running time of any randomized algorithm on worst-case input is equal to the average-case running time of any deterministic algorithm for the worst-case distribution of inputs. Yao’s principle has become a fundamental technique for reasoning about randomized algorithms and complexity, and has also been applied in areas such as property testing and learning theory.
\par
Around this time Yao also made fundamental contributions to the theory of data structures. His 1978 paper, “Should tables be sorted?” [2] introduced the cell-probe model, an abstract model of data structures where the cost of a computation is measured by the total number of memory accesses. This model has been widely used in creating lower bound proofs of algorithms.
\par
Yao spent a year as a Professor in the Computer Science Division of the University of California, Berkeley, and subsequently returned to Stanford as a full Professor in 1982. During the early 1980’s, Yao produced a number of papers which had a lasting impact on the foundations of cryptography, computer security, computational complexity and randomized computation. This work was significant not only for results obtained, but also for the introduction of problems, models and techniques which are now considered fundamental in their respective areas.
\par
His 1981 paper with Danny Dolev, “On the security of public-key protocols,” [8] introduced a formal model for symbolic reasoning about security protocols. Since its introduction, this “Dolev-Yao model” has been the starting point for most work done on symbolic security, including recent work on the security of complexity-based cryptography, This continues to be an active area of research. Yao also made significant contributions to cryptography and complexity-based approaches to security. In 1982 he published “Theory and applications of trapdoor functions” [7] and “Protocols for secure computations” [5]. These works, which were introduced at the same conference, stand as seminal contributions in cryptography and secure computation.
\par
The first of these papers addresses the then newly-emerging field of public-key cryptography from a theoretical perspective, lays the foundation for a theory of computational randomness, and initiates a study of its relationship to computational hardness. Yao provides a definition of pseudorandom number generator which is based on computational complexity, and proposes a definition of “perfect”—in current terminology, “pseudorandom”—probability distribution ensembles. (An ensemble is perfect if it cannot be distinguished from a truly random ensemble by any feasible distinguisher, where such distinguishers are formalized using the notion of a polynomial time randomized algorithm.) Yao relates his notion of pseudorandomness to the idea of a statistical test, a notion already used in the study of pseudorandom number generators, and shows that one particular test, known as the next-bit test, is adequate for characterizing pseudorandomness. Having defined perfect ensembles, Yao then defined a pseudorandom number generator as an efficient randomized algorithm which uses a limited number of truly random bits in order to output a sample from a perfect distribution whose size is polynomial in the number of random bits used.
\par
The next fundamental contribution of the paper addresses the question of what computational assumptions are adequate for the existence of pseudorandom number generators. Advances in public-key cryptography indicated that secure encryption could be based on the assumed hardness of certain computational problems such as quadratic residuosity, or problems related to factoring integers. Yao asked whether one could make a general assumption about computational hardness which could be used to obtain pseudorandomness and hence, through standard techniques, cryptographic security. For this he formalized the notion of a one-way function that is easy to compute but hard to invert for a large fraction of inputs. He proved that one-way functions with certain properties may be used to construct pseudorandom number generators. This inspired a series of important results that refined Yao’s work, and it continues to be an area of active research. The contributions of this paper to pseudorandomness form an essential component of modern cryptography. In addition, the paper proposes a new field of computational information theory which refines Shannon’s theory by taking computational resources into account. Yao gives a definition of computational entropy, and uses it to give a characterization of encryption security. This definition of entropy is now important in areas such as leakage-resilient cryptography.
\par
The second paper introduces a new paradigm for secure function evaluation, and introduces the famous “Millionaires’ Problem”. Yao gives a protocol which allows two parties, each holding a number, to determine who has the larger number without revealing the actual values. The Millionaires’ Problem is a two-party instance of a more general class of secure multiparty computation problems which are now essential to the study of secure cryptographic protocols. With the advent of wide-scale distributed computing and the ubiquity of cryptographic protocols, Yao’s contributions in this area have had a significant impact on networked computing.
\par
In the 1980’s, Professor Yao introduced models and techniques whose ramifications are still being felt in research in complexity, computational randomness, cryptography, and security. Some of his most influential ideas were disseminated in lectures building on his published results. One example is the XOR-lemma, which uses computational hardness to produce pseudorandomness. Yao addressed whether the hardness of a problem may be amplified by combining multiple instances of the problem, in this case through the use of the bitwise exclusive-OR operation. While interesting in its own right, the XOR-lemma is an essential technique in the area of derandomization, which seeks generic methods for eliminating the need for randomness in the efficient solution of algorithmic problems.  More generally, it helps determine whether certain classes of problems that are solved efficiently with randomization can instead be solved deterministically.
\par
A second example is the garbled circuit technique, an important tool in secure multiparty computation which was used implicitly by Yao in his 1982 secure computation paper as well as in a 1986 paper “How to generate and exchange secrets” [6]. Recent advances in computing power have made the garbled circuit technique practical for large-scale computational problems, for example in privacy-preserving matching in DNA databases.
\par
In 1986, Yao moved to Princeton University, where he became the William and Edna Macaleer Professor of Engineering and Applied Science. During this period he continued his work on the foundations of cryptography. He also built on previous work in areas such as decision tree and communication complexity. Yao made substantial contributions to the theory of lower bounds for algebraic decision trees, an area he established in a 1982 Journal of Algorithms paper [9] co-authored with J.M. Steele. This work exploited deep relationships between algebraic decision trees and mathematical results in algebraic geometry. He also investigated the use of randomization in decision trees. Professor Yao introduced the theory of communication complexity in a 1979 paper “Some complexity questions related to distributive computing” [3].  In his 1993 paper, “Quantum circuit complexity”[4] he extended communication complexity to quantum computing. Starting in the 1990’s, Professor Yao began to work extensively on quantum computing, communication and information theory. He continues to make significant contributions in these areas.
\par
Andrew Yao became a Professor in the Center for Advanced Study and Director of the Institute for Theoretical Computer Science at Tsinghua University, Beijing, in 2004. Since 2005 he has also been Distinguished Professor-at-Large of the Chinese University of Hong Kong. His recent contributions include work in security protocols, universally composable secure computation, quantum computing, and the theory of algorithms.
\par
Yao is active in graduate supervision, and has mentored over twenty Ph.D. students. He is married to Professor Frances Yao, a computer scientist and leading researcher in computational geometry, algorithms and cryptography.
\par
Author: Bruce Kapron
\par
\vspace{1cm}
\textbf{Short Annotated Bibliography}\par
\vspace{1cm}
1.Yao, Andrew Chi-Chih, “Probabilistic Computations: Toward a Unified Measure of Complexity” (Extended Abstract), 18th Annual Symposium on Foundations of Computer Science (FOCS ’77), IEEE Computer Society, 1977, pp. 222-227. \par
This paper considers probability in computation from two perspectives: probability distributions on inputs, and the use randomization in algorithms. The two perspectives are unified with Yao’s min-max principle, which states that the worst-case expected running time of a randomized algorithm for a problem is equal to the average-case running time of any deterministic algorithm, for the worst-case distribution on problem inputs.
\par
2.Yao, Andrew Chi-Chih, “Should Tables Be Sorted?” (Extended Abstract), 19th Annual Symposium on Foundations of Computer Science (FOCS ’78). IEEE Computer Society, 1978, pp. 22-27.\par
In this paper Yao introduces the cell-probe model for the analysis of data structures in which the cost of a computation is the number of accesses to a random access memory with cell size log n.
\par

3.Yao, Andrew Chi-Chih, “Some Complexity Questions Related to Distributive Computing” (Preliminary Report), Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC ’79), ACM Press, 1979, pp. 209-213, available here.\par

4.Yao, Andrew Chi-Chih, “Quantum Circuit Complexity,” 34th Annual Symposium on Foundations of Computer Science (FOCS ’93), IEEE Computer Society, 1993, pp. 352-361. \par
The first of these two papers introduces communication complexity, a measure which has proven to be useful in obtaining complexity bounds in areas including parallel computation, circuits, and data structures. The second paper extends the classical model of the first paper to situations in which participants in a protocol may exchange quantum bits.
\par

5.Yao, Andrew Chi-Chih, “Protocols for Secure Computations” (Extended Abstract), 23rd Annual Symposium on Foundations of Computer Science (FOCS ’82), IEEE Computer Society, 1982, pp. 160-164.\par

6.Yao, Andrew Chi-Chih, “How to Generate and Exchange Secrets” (Extended Abstract), 27th Annual Symposium on Foundations of Computer Science (FOCS ’87), IEEE Computer Society, 1986, pp. 162-167. \par

The first of these two papers introduces secure function evaluation, and gives a protocol for the famous Millionaires’ Problem. In talks related to these papers Yao introduced a technique for secure computation known as garbled circuits.
\par

7.Yao, Andrew Chi-Chih, “Theory and Applications of Trapdoor Functions” (Extended Abstract), 23rd Annual Symposium on Foundations of Computer Science (FOCS ’82), IEEE Computer Society, 1982, pp. 80-91. \par

This influential paper introduces a number of notions and techniques that are essential to modern complexity-based cryptography, including computational indistinguishability as a basis for characterizing pseudorandom generators, and the use of one-way functions as a complexity-theoretic basis for obtaining cryptographic security via pseudorandomness. Yao also introduces ideas which have had a major impact in other areas such as computational information theory and derandomization.
\par

8.Dolev, Danny and Andrew Chi-Chih Yao, “On the security of public key protocols,” IEEE Transactions on Information Theory, Vol. 29, Num. 2, 1983, pp. 198-207. \par
The authors introduce a model for the analysis of cryptography-based security protocols which has become known as the Dolev-Yao model, and is the basis for many current approaches to formal verification of such protocols.
\par

9.Steele, J. Michael and Andrew Chi-Chih Yao, “Lower Bounds for Algebraic Decision Trees,” Journal of Algorithms, Vol. 3, Num. 1, 1982, pp. 1-8.\par

10.Yao, Andrew Chi-Chih, “Lower Bounds to Randomized Algorithms for Graph Properties,” Journal of Computing Systems Science, Vol. 42, Num. 3, 1991, pp.  267-287. \par
Professor Yao has made extensive contributions to structured models of computation, including decision trees. The first of these two papers proposes algebraic decision trees, a generalization of the linear decision trees of Dobkin and Lipton. The second paper considers randomization in the Boolean decision tree model for deciding graph properties.
\par

\section{2021年理论计算科学和离散数学领域学者获Abel奖}
3月17日，2021年阿贝尔奖揭晓。挪威科学和文学院决定将2021年阿贝尔奖授予来自匈牙利，布达佩斯罗兰大学的László Lovász 和来自美国，普林斯顿高等研究院的 Avi Wigderson，以表彰两位科学家在理论计算机科学和离散数学方面做出的杰出贡献，以及在将之塑造为现代数学中心领域中发挥的主导作用。获奖者将分享750万挪威克朗的奖金(约合580万人民币)。\par

理论计算机科学 (TCS，全称theory computer science) 是研究计算的能力和局限性的科学。其根源可追溯至 Kurt Gdel、AlonzoChurch、Alan Turing 和 John von Neumann 所做的基础性研究，这些研究推动了真正的物理计算机的发展。TCS 包含两个互补的分支学科，即算法设计(为大量计算问题开发有效方法)和计算复杂性(证明算法效率的固有限制)。\par

自然离散数学(discrete mathematic)和 TCS 一直是紧密联系的两个领域。虽然这两个领域都从更传统的数学领域中获益匪浅，但其对传统数学领域的反向影响也越来越大。 TCS 的应用、概念和技术带来了新的挑战，开辟了新的研究方向，解决了纯数学和应用数学中的重要开放性问题。\par

在过去几十年中，Lászlé Lovász 和 Avi Wigderson一直是推动实现相关发展的主导力量。Lászlé Lovász 与 Arjen Lenstra 和 Hendrik Lenstra一起开发出了 LLL 格基约减算法。给定一个高维整数格(网格)，此算法可以为之找到一个不错的近乎正交基。除了因式分解有理多项式的算法等一些应用之外，LLL 算法也是一个受密码专家欢迎的工具，并成功破解了所提出的几个加密系统。令人惊讶的是，LLL 算法的分析还用于设计和保证较新的格基加密系统的安全性，这些系统甚至能够抵御量子计算机的攻击。\par

Avi Wigderson 对计算复杂性的各个方面，特别是随机性在计算中的作用，做出了广泛而深刻的贡献。随机算法是指通过抛硬币的方法，以高概率计算正确解的算法。Wigderson雨合作者证明了P=BPP这一猜想，这意味着每一种随机算法都可以去随机化。Wigderson与Impagliazzo 和 Valentine Kabanets 的后续研究进一步证明了即使是对于有已知的随机算法的具体问题，有效的确定性算法也意味着必须存在这样一个难解的问题。\par

阿贝尔委员会主席 Hans Munthe-Kaas 表示，“在过去几十年中，Lovász 和 Wigderson 一直是推动实现相关发展的主导力量。他们的研究在很多方面是相互交错的，并都对理解计算中的随机性和探索高效计算的边界做出了巨大贡献。”
\par
他说：“正是由于这两位所做出的突破性贡献，离散数学和相对”年轻的理论计算机科学领域现已牢固确立为现代数学的中心领域。\par

\textbf{关于阿贝尔奖 Abel prize}\par

阿贝尔奖设立于2002年1月1日，于2003年6月3日首次颁发。阿贝尔奖与菲尔兹奖、沃尔夫奖并称为国际最高数学“三大奖”。\par

（文章来源：\url{https://baijiahao.baidu.com/s?id=1694544933927331714&wfr=spider&for=pc}）

\section{ZUC}
首先我们把ZUC看成一个加密盒子，一个黑盒子，看看ZUC是做什么的。输入一个128 bits的初始密钥，一个128 bits的初始向量，生成一个32bit的密钥流(也就是生成一个密钥字流(key words)),如图\ref{zuc-box}所示.\par

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{zuc.png}
	\caption{ZUC算法}
	\label{zuc-box}
\end{figure}

\subsection{密钥装载}
$k=k_0 \Arrowvert k_1 \Arrowvert \ldots \Arrowvert k_{15} $,$k_i$为8 bits长。\par
$iv=iv_0 \Arrowvert iv_1 \Arrowvert \ldots \Arrowvert iv_{15} $,$iv_i$为8 bits长。\par
$D=d_0 \Arrowvert d_1 \Arrowvert \ldots \Arrowvert d_{15} $,$d_i$为15 bits长,D为240 bits常量。\par
$s_i=k_i \Arrowvert d_i \Arrowvert iv_i, 0\leq i \leq 15 $,$s_i$为31 bits长,用于初始化LFSR。\par

\subsection{初始化阶段}
密钥装载完成$s_0,\ldots,s_15$初始化，并且$R_1,R_2$全为0，以下过程执行32次。\par
$
\begin{cases}
	BitReconstruction(); \\
	W=F(X_0,X_1,X_2); \\
	LFSRWithInitialisationMode(u);
\end{cases}
$

其中$u=W>>1$，也就是W去掉最低位得u。\par
其中LFSR的初始化过程如下：\\
LFSRWithInitialisationMode(u)\\
\{\\
 (1) $v=2^{15}s_{15}+2^{17}s_{13}+2^{21}s_{10}+2^{20}s_{4}+(1+2^8)s_0 \pmod{2^{31}-1}$;\\
 (2) $s_{16}=(v+u) \pmod{2^{31}-1}$;\\
 (3) if $s_{16}=0,$ then set $s_{16}=2^{31}-1$;\\
 (4) $(s_1,s_2,\ldots,s_{15},s_{16}) \longrightarrow (s_0,s_1,\ldots,s_{14},s_{15})$;\\
\}
\par

\subsection{工作阶段}
执行一次：
$
\begin{cases}
	BitReconstruction(); \\
	W=F(X_0,X_1,X_2); \\
	LFSRWithInitialisationMode(u);
\end{cases}
$
\par
循环执行：
$
\begin{cases}
BitReconstruction(); \\
Z=F(X_0,X_1,X_2)\oplus X_3; \\
LFSRWithWorkMode();
\end{cases}
$
\par
其中LFSR在工作模式下的过程如下：\\
LFSRWithInitialisationMode(u)\\
\{\\
(1) $v=2^{15}s_{15}+2^{17}s_{13}+2^{21}s_{10}+2^{20}s_{4}+(1+2^8)s_0 \pmod{2^{31}-1}$;\\
(2) if $s_{16}=0,$ then set $s_{16}=2^{31}-1$;\\
(3) $(s_1,s_2,\ldots,s_{15},s_{16}) \longrightarrow (s_0,s_1,\ldots,s_{14},s_{15})$;\\
\}

\subsection{F函数}
$L_1,L_2$是两个线性变换，$S=(S_0,S_1,S_2,S_3)=(S_0,S_1,S_0,S_1)$,$S_i$是个8入8出的盒子，查表方法是高四比特为行号，低4比特为列号。具体可以看英文标准给出的示例比较易懂。

\subsection{ZUC设计理念及准则 }
我就ZUC的设计理念去邮件询问了设计者之一冯秀涛博士，本部分内容摘自其邮件中提供的ppt(截图见\ref{zuc-fxt-ppt})。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{zuc-fxt-ppt.png}
	\caption{冯秀涛博士ppt}
	\label{zuc-fxt-ppt}
\end{figure}

\subsubsection{设计理念}
我们主要采用分解+融合的设计思想，即将算法分解成若干部件，每个部件偏重某些攻击方法：
\begin{itemize}
	\item LFSR:采用非2特征素域设计，其在$F_2$上是非线性的，可以抵抗当前许多针对二元域上的密码攻击方法，譬如区分分析、相关分析、代数分析等。
	\item 比特重组：打破素域$F_p$上的代数结构，使得针对$F_p$上的密码攻击方法变得十分困难，譬如代数分析。
	\item 非线性函数F：借鉴分组密码设计思想，采用S盒和最佳扩展准则的线性变换，进一步打破$F_p$上的代数结构，同时增强抵抗传统基于$F_2$的密码攻击的能力，譬如区分分析、相关分析等。
\end{itemize}
最后通过它们以及不同代数结构之间相互融合达到整体安全性的目的。

\subsubsection{设计准则}
LFSR的设计遵循如下准则：
\begin{itemize}
	\item 为了保证序列源具有大的周期和好的统计特性，其特征多项式$f(x)$须是$F_p$上的本原多项式；
	\item 为了便于快速软硬件实现，$f(x)$的非零项系数的二进制汉明重量必须尽可能的低；
	\item 为了保证在模$2^{31}-1$和模2之间低的比特符合率，$f(x)$的所有非零系数的汉明总量之和必须为奇数；
	\item $f(x)$的所有非零项系数中1的位置尽可能的两两不同；
	\item $f(x)$没有明显的低权重低次数的倍式。
\end{itemize}
基于以上准则，我们选择了如下本原多项式：
\[f(x)=x^{16}-(2^{15}x^{15}+ 2^{17}x^{13}+2^{21}x^{10}+2^{20}x^4+(2^8 -1))\]

比特重组的设计主要遵循以下准则：
\begin{itemize}
	\item 便于软硬件实现；
	\item 4个32比特输出必须拥有好的统计特性；
	\item 4个32比特的输出在不同时刻之间重叠的比特数尽可能的低。
\end{itemize}

非线性函数F的设计准则如下：
\begin{itemize}
	\item 带64比特记忆；
	\item 使用S盒提高非线性；
	\item 使用具有好的扩散特性的线性变换；
	\item 每个记忆单元的更新必须同时依赖3个以上独立寄存器单元的值；
	\item 非线性函数F的输出必须是平衡的且具有好的随机性；
	\item 非线性函数F应该便于软硬件实现，且具有低的硬件实现代价。
\end{itemize}

\section{finite field}

A field with a finite number of elements. First considered by E. Galois.

The number of elements of any finite field is a power $p^n$ of a prime number $p$, which is the [[Characteristic of a field|characteristic]] of this field. For any prime number $p$ and any natural number $n$ there exists a (unique up to an isomorphism) field of $p^n$ elements. It is denoted by $\mathrm{GF}(p^n)$ or by $\mathbb{F}_{p^n}$. The field $\mathrm{GF}(p^m)$ contains the field $\mathrm{GF}(p^n)$ as a subfield if and only if $m$ is divisible by $n$. In particular, any field $\mathrm{GF}(p^n)$ contains the field $\mathrm{GF}(p)$, which is called the [[prime field]] of characteristic $p$. The field $\mathrm{GF}(p)$ is isomorphic to the field $\mathbb{Z}/p\mathbb{Z}$ of residue classes of the ring of integers modulo $p$. In any fixed [[Algebraic closure|algebraic closure]] $\Omega$ of $\mathrm{GF}(p)$ there exists exactly one subfield $\mathrm{GF}(p^n)$ for each $n$. The correspondence $n \leftrightarrow \mathrm{GF}(p^n)$ is an isomorphism between the lattice of natural numbers with respect to division and the lattice of finite algebraic extensions (in $\Omega$) of $\mathrm{GF}(p)$ with respect to inclusion. The lattice of finite algebraic extensions of any Galois field within its fixed algebraic closure is such a lattice.

The algebraic extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$ is simple, i.e. there exists a primitive element $\alpha \in \mathrm{GF}(p^n)$ such that $\mathrm{GF}(p^n) = \mathrm{GF}(p)(\alpha)$. Such an $\alpha$ will be any root of any irreducible polynomial of degree $n$ from the ring $\mathrm{GF}(p)[X]$. The number of primitive elements of the extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$ equals
$$
\sum_{d|n} \mu(d) p^{n/d}
$$
where $\mu$ is the [[Möbius function|Möbius function]]. The additive group of the field $\mathrm{GF}(p^n)$ is naturally endowed with the structure of an $n$-dimensional vector space over $\mathrm{GF}(p)$. As a basis one may take $1,\alpha,\ldots,\alpha^{n-1}$. The non-zero elements of $\mathrm{GF}(p^n)$ form a multiplicative group, $\mathrm{GF}(p^n)^*$, of order $p^n-1$, i.e. each element of $\mathrm{GF}(p^n)^*$ is a root of the polynomial $X^{p^n-1}-1$. The group $\mathrm{GF}(p^n)^*$ is cyclic, and its generators are the primitive roots of unity of degree $p^n-1$, the number of which is $\phi(p^n-1)$, where $\phi$ is the [[Euler function|Euler function]]. Each primitive root of unity of degree $p^n-1$ is a primitive element of the extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$, but the converse is not true. More exactly, out of the
$$
\frac{1}{n} \sum_{d|n} \mu(d) p^{n/d}
$$
irreducible unitary polynomials of degree $n$ over $\mathrm{GF}(p)$ there are $\phi(p^n-1)/n$ polynomials of which the roots are generators of $\mathrm{GF}(p^n)$.

The set of elements of $\mathrm{GF}(p^n)$ coincides with the set of roots of the polynomial $X^{p^n} - X$ in $\Omega$, i.e. $\mathrm{GF}(p^n)$ is characterized as the subfield of elements from $\Omega$ that are invariant with respect to the automorphism $\tau : x \mapsto x^{p^n}$, which is known as the Frobenius automorphism. If $\mathrm{GF}(p^m) \supset \mathrm{GF}(p^n)$, the extension $\mathrm{GF}(p^m)/\mathrm{GF}(p^n)$ is normal (cf. [[Extension of a field|Extension of a field]]), and its [[Galois group|Galois group]] $\mathrm{Gal}\left({\mathrm{GF}(p^m)/\mathrm{GF}(p^n)}\right)$ is cyclic of order $m/n$. The automorphism $\tau$ may be taken as the generator of $\mathrm{Gal}\left({\mathrm{GF}(p^m)/\mathrm{GF}(p^n)}\right)$.

[[Category:Field theory and polynomials]]

\section{GF(2)上的本原多项式}
信息来源于\url{https://www.partow.net/programming/polynomials/index.html}。\\
$x^2 + x^1 + 1$\\
$x^3 + x^1 + 1$\\
$x^4 + x^1 + 1$\\
$x^5 + x^2 + 1$\\
$x^5 + x^4 + x^2 + x^1 + 1$\\
$x^5 + x^4 + x^3 + x^2 + 1$\\
$x^6 + x^1 + 1$\\
$x^6 + x^5 + x^2 + x^1 + 1$\\
$x^6 + x^5 + x^3 + x^2 + 1$\\
$x^7 + x^1 + 1$\\
$x^7 + x^3 + 1$\\
$x^7 + x^3 + x^2 + x^1 + 1$\\
$x^7 + x^4 + x^3 + x^2 + 1$\\
$x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1$\\
$x^7 + x^6 + x^3 + x^1 + 1$\\
$x^7 + x^6 + x^4 + x^2 + 1$\\
$x^7 + x^6 + x^5 + x^2 + 1$\\
$x^7 + x^6 + x^5 + x^4 + x^2 + x^1 + 1$\\
$x^8 + x^4 + x^3 + x^2 + 1$\\
$x^8 + x^5 + x^3 + x^1 + 1$\\
$x^8 + x^6 + x^4 + x^3 + x^2 + x^1 + 1$\\
$x^8 + x^6 + x^5 + x^1 + 1$\\
$x^8 + x^6 + x^5 + x^2 + 1$\\
$x^8 + x^6 + x^5 + x^3 + 1$\\
$x^8 + x^7 + x^6 + x^1 + 1$\\
$x^8 + x^7 + x^6 + x^5 + x^2 + x^1 + 1$\\
$x^9 + x^4 + 1$\\
$x^9 + x^5 + x^3 + x^2 + 1$\\
$x^9 + x^6 + x^4 + x^3 + 1$\\
$x^9 + x^6 + x^5 + x^3 + x^2 + x^1 + 1$\\
$x^9 + x^6 + x^5 + x^4 + x^2 + x^1 + 1$\\
$x^9 + x^7 + x^6 + x^4 + x^3 + x^1 + 1$\\
$x^9 + x^8 + x^4 + x^1 + 1$\\
$x^9 + x^8 + x^5 + x^4 + 1$\\
$x^9 + x^8 + x^6 + x^5 + 1$\\
$x^9 + x^8 + x^6 + x^5 + x^3 + x^1 + 1$\\
$x^9 + x^8 + x^7 + x^2 + 1$\\
$x^9 + x^8 + x^7 + x^3 + x^2 + x^1 + 1$\\
$x^9 + x^8 + x^7 + x^6 + x^5 + x^1 + 1$\\
$x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + 1$\\
$x^{10} + x^3 + 1$\\
$x^{10} + x^4 + x^3 + x^1 + 1$\\
$x^{10} + x^6 + x^5 + x^3 + x^2 + x^1 + 1$\\
$x^{10} + x^8 + x^3 + x^2 + 1$\\
$x^{10} + x^8 + x^4 + x^3 + 1$\\
$x^{10} + x^8 + x^5 + x^1 + 1$\\
$x^{10} + x^8 + x^5 + x^4 + 1$\\
$x^{10} + x^8 + x^7 + x^6 + x^5 + x^2 + 1$\\
$x^{10} + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^1 + 1$\\
$x^{10} + x^9 + x^4 + x^1 + 1$\\
$x^{10} + x^9 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1$\\
$x^{10} + x^9 + x^8 + x^6 + x^3 + x^2 + 1$\\
$x^{10} + x^9 + x^8 + x^6 + x^5 + x^1 + 1$\\
$x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1$\\
$x^{11} + x^2 + 1$\\
$x^{11} + x^5 + x^3 + x^1 + 1$\\
$x^{11} + x^5 + x^3 + x^2 + 1$\\
$x^{11} + x^6 + x^5 + x^1 + 1$\\
$x^{11} + x^7 + x^3 + x^2 + 1$\\
$x^{11} + x^8 + x^5 + x^2 + 1$\\
$x^{11} + x^8 + x^6 + x^5 + x^4 + x^1 + 1$\\
$x^{11} + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1$\\
$x^{11} + x^9 + x^4 + x^1 + 1$\\
$x^{11} + x^9 + x^8 + x^7 + x^4 + x^1 + 1$\\
$x^{11} + x^{10} + x^3 + x^2 + 1$\\
$x^{11} + x^{10} + x^7 + x^4 + x^3 + x^1 + 1$\\
$x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + 1$\\
$x^{11} + x^{10} + x^9 + x^8 + x^3 + x^1 + 1$\\
$x^{12} + x^6 + x^4 + x^1 + 1$\\
$x^{12} + x^9 + x^3 + x^2 + 1$\\
$x^{12} + x^9 + x^8 + x^3 + x^2 + x^1 + 1$\\
$x^{12} + x^{10} + x^9 + x^8 + x^6 + x^2 + 1$\\
$x^{12} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^4 + x^2 + 1$\\
$x^{12} + x^{11} + x^6 + x^4 + x^2 + x^1 + 1$\\
$x^{12} + x^{11} + x^9 + x^5 + x^3 + x^1 + 1$\\
$x^{12} + x^{11} + x^9 + x^7 + x^6 + x^4 + 1$\\
$x^{12} + x^{11} + x^9 + x^7 + x^6 + x^5 + 1$\\
$x^{12} + x^{11} + x^9 + x^8 + x^7 + x^4 + 1$\\
$x^{12} + x^{11} + x^9 + x^8 + x^7 + x^5 + x^2 + x^1 + 1$\\
$
x^{12} + x^{11} + x^{10} + x^5 + x^2 + x^1 + 1\\
x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^4 + x^3 + x^1 + 1\\
x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + 1\\
x^{13} + x^4 + x^3 + x^1 + 1\\
x^{13} + x^9 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{13} + x^9 + x^8 + x^7 + x^5 + x^1 + 1\\
x^{13} + x^{10} + x^9 + x^7 + x^5 + x^4 + 1\\
x^{13} + x^{10} + x^9 + x^8 + x^6 + x^3 + x^2 + x^1 + 1\\
x^{13} + x^{11} + x^8 + x^7 + x^4 + x^1 + 1\\
x^{13} + x^{11} + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{13} + x^{12} + x^6 + x^5 + x^4 + x^3 + 1\\
x^{13} + x^{12} + x^8 + x^7 + x^6 + x^5 + 1\\
x^{13} + x^{12} + x^9 + x^8 + x^4 + x^2 + 1\\
x^{13} + x^{12} + x^{10} + x^8 + x^6 + x^4 + x^3 + x^2 + 1\\
x^{13} + x^{12} + x^{11} + x^5 + x^2 + x^1 + 1\\
x^{13} + x^{12} + x^{11} + x^8 + x^7 + x^6 + x^4 + x^1 + 1\\
x^{13} + x^{12} + x^{11} + x^9 + x^5 + x^3 + 1\\
x^{14} + x^8 + x^6 + x^1 + 1\\
x^{14} + x^{10} + x^6 + x^1 + 1\\
x^{14} + x^{10} + x^9 + x^7 + x^6 + x^4 + x^3 + x^1 + 1\\
x^{14} + x^{11} + x^6 + x^1 + 1\\
x^{14} + x^{11} + x^9 + x^6 + x^5 + x^2 + 1\\
x^{14} + x^{12} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + 1\\
x^{14} + x^{12} + x^{11} + x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + x^1 + 1\\
x^{14} + x^{12} + x^{11} + x^{10} + x^9 + x^7 + x^4 + x^3 + 1\\
x^{14} + x^{13} + x^6 + x^5 + x^3 + x^1 + 1\\
x^{14} + x^{13} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{14} + x^{13} + x^{11} + x^6 + x^5 + x^4 + x^2 + x^1 + 1\\
x^{14} + x^{13} + x^{11} + x^8 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^7 + x^6 + x^1 + 1\\
x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^6 + x^5 + 1\\
x^{15} + x^1 + 1\\
x^{15} + x^4 + 1\\
x^{15} + x^7 + 1\\
x^{15} + x^7 + x^6 + x^3 + x^2 + x^1 + 1\\
x^{15} + x^{10} + x^5 + x^1 + 1\\
x^{15} + x^{10} + x^5 + x^4 + 1\\
x^{15} + x^{10} + x^5 + x^4 + x^2 + x^1 + 1\\
x^{15} + x^{10} + x^9 + x^7 + x^5 + x^3 + 1\\
x^{15} + x^{10} + x^9 + x^8 + x^5 + x^3 + 1\\
x^{15} + x^{11} + x^7 + x^6 + x^2 + x^1 + 1\\
x^{15} + x^{12} + x^3 + x^1 + 1\\
x^{15} + x^{12} + x^5 + x^4 + x^3 + x^2 + 1\\
x^{15} + x^{12} + x^{11} + x^8 + x^7 + x^6 + x^4 + x^2 + 1\\
x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1\\
x^{16} + x^9 + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1\\
x^{16} + x^{12} + x^3 + x^1 + 1\\
x^{16} + x^{12} + x^7 + x^2 + 1\\
x^{16} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^6 + x^1 + 1\\
x^{16} + x^{13} + x^{12} + x^{11} + x^7 + x^6 + x^3 + x^1 + 1\\
x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^6 + x^2 + x^1 + 1\\
x^{16} + x^{14} + x^{10} + x^8 + x^3 + x^1 + 1\\
x^{16} + x^{14} + x^{13} + x^{12} + x^6 + x^5 + x^3 + x^2 + 1\\
x^{16} + x^{14} + x^{13} + x^{12} + x^{10} + x^7 + 1\\
x^{16} + x^{15} + x^{10} + x^6 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{16} + x^{15} + x^{11} + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1\\
x^{16} + x^{15} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{16} + x^{15} + x^{11} + x^{10} + x^9 + x^6 + x^2 + x^1 + 1\\
x^{16} + x^{15} + x^{11} + x^{10} + x^9 + x^8 + x^6 + x^4 + x^2 + x^1 + 1\\
x^{17} + x^3 + 1\\
x^{17} + x^3 + x^2 + x^1 + 1\\
x^{17} + x^5 + 1\\
x^{17} + x^6 + 1\\
x^{17} + x^8 + x^4 + x^3 + 1\\
x^{17} + x^8 + x^7 + x^6 + x^4 + x^3 + 1\\
x^{17} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^3 + x^2 + 1\\
x^{17} + x^{12} + x^6 + x^3 + x^2 + x^1 + 1\\
x^{17} + x^{12} + x^9 + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{17} + x^{12} + x^9 + x^7 + x^6 + x^4 + x^3 + x^2 + 1\\
x^{17} + x^{14} + x^{11} + x^7 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{17} + x^{15} + x^{13} + x^{11} + x^9 + x^7 + x^5 + x^3 + 1\\
x^{17} + x^{15} + x^{13} + x^{11} + x^9 + x^7 + x^6 + x^4 + x^2 + x^1 + 1\\
x^{17} + x^{16} + x^3 + x^1 + 1\\
x^{18} + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{18} + x^7 + 1\\
x^{18} + x^7 + x^5 + x^2 + x^1 + 1\\
x^{18} + x^8 + x^2 + x^1 + 1\\
x^{18} + x^9 + x^7 + x^6 + x^5 + x^4 + 1\\
x^{18} + x^9 + x^8 + x^6 + x^5 + x^4 + x^2 + x^1 + 1\\
x^{18} + x^9 + x^8 + x^7 + x^6 + x^4 + x^2 + x^1 + 1\\
x^{18} + x^{10} + x^7 + x^5 + 1\\
x^{18} + x^{10} + x^8 + x^5 + 1\\
x^{18} + x^{10} + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{18} + x^{10} + x^9 + x^3 + 1\\
x^{18} + x^{13} + x^6 + x^4 + 1\\
x^{18} + x^{15} + x^5 + x^2 + 1\\
x^{18} + x^{15} + x^9 + x^2 + 1\\
x^{19} + x^5 + x^2 + x^1 + 1\\
x^{19} + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^6 + x^2 + x^1 + 1\\
x^{19} + x^6 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^6 + x^5 + x^4 + x^3 + x^2 + 1\\
x^{19} + x^7 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^8 + x^7 + x^5 + 1\\
x^{19} + x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^9 + x^8 + x^5 + 1\\
x^{19} + x^9 + x^8 + x^6 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^9 + x^8 + x^7 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^{11} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1\\
x^{19} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1\\
x^{19} + x^{16} + x^{13} + x^{10} + x^7 + x^4 + x^1 + 1\\
x^{20} + x^3 + 1\\
x^{20} + x^9 + x^5 + x^3 + 1\\
x^{20} + x^{11} + x^8 + x^6 + x^3 + x^2 + 1\\
x^{20} + x^{14} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^4 + 1\\
x^{20} + x^{17} + x^{14} + x^{10} + x^7 + x^4 + x^3 + x^2 + 1\\
x^{20} + x^{19} + x^4 + x^3 + 1\\
x^{21} + x^2 + 1\\
x^{21} + x^8 + x^7 + x^4 + x^3 + x^2 + 1\\
x^{21} + x^{10} + x^6 + x^4 + x^3 + x^2 + 1\\
x^{21} + x^{13} + x^5 + x^2 + 1\\
x^{21} + x^{14} + x^7 + x^2 + 1\\
x^{21} + x^{14} + x^7 + x^6 + x^3 + x^2 + 1\\
x^{21} + x^{14} + x^{12} + x^7 + x^6 + x^4 + x^3 + x^2 + 1\\
x^{21} + x^{15} + x^{10} + x^9 + x^5 + x^4 + x^3 + x^2 + 1\\
x^{21} + x^{20} + x^{19} + x^{18} + x^5 + x^4 + x^3 + x^2 + 1\\
x^{22} + x^1 + 1\\
x^{22} + x^9 + x^5 + x^1 + 1\\
x^{22} + x^{14} + x^{13} + x^{12} + x^7 + x^3 + x^2 + x^1 + 1\\
x^{22} + x^{17} + x^9 + x^7 + x^2 + x^1 + 1\\
x^{22} + x^{17} + x^{13} + x^{12} + x^8 + x^7 + x^2 + x^1 + 1\\
x^{22} + x^{20} + x^{18} + x^{16} + x^6 + x^4 + x^2 + x^1 + 1\\
x^{23} + x^5 + 1\\
x^{23} + x^5 + x^4 + x^1 + 1\\
x^{23} + x^{11} + x^{10} + x^7 + x^6 + x^5 + 1\\
x^{23} + x^{12} + x^5 + x^4 + 1\\
x^{23} + x^{15} + x^{10} + x^9 + x^7 + x^5 + x^4 + x^3 + 1\\
x^{23} + x^{16} + x^{13} + x^6 + x^5 + x^3 + 1\\
x^{23} + x^{17} + x^{11} + x^5 + 1\\
x^{23} + x^{17} + x^{11} + x^9 + x^8 + x^5 + x^4 + x^1 + 1\\
x^{23} + x^{18} + x^{16} + x^{13} + x^{11} + x^8 + x^5 + x^2 + 1\\
x^{23} + x^{21} + x^7 + x^5 + 1\\
x^{24} + x^7 + x^2 + x^1 + 1\\
x^{24} + x^{21} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{10} + x^9 + x^5 + x^4 + x^1 + 1\\
x^{24} + x^{22} + x^{20} + x^{18} + x^{16} + x^{14} + x^{11} + x^9 + x^8 + x^7 + x^5 + x^4 + 1\\
x^{25} + x^3 + 1\\
x^{25} + x^3 + x^2 + x^1 + 1\\
x^{25} + x^{11} + x^9 + x^8 + x^6 + x^4 + x^3 + x^2 + 1\\
x^{25} + x^{12} + x^4 + x^3 + 1\\
x^{25} + x^{12} + x^{11} + x^8 + x^7 + x^6 + x^4 + x^3 + 1\\
x^{25} + x^{17} + x^{10} + x^3 + x^2 + x^1 + 1\\
x^{25} + x^{18} + x^{12} + x^{11} + x^6 + x^5 + x^4 + x^3 + 1\\
x^{25} + x^{20} + x^5 + x^3 + 1\\
x^{25} + x^{20} + x^{16} + x^{11} + x^5 + x^3 + x^2 + x^1 + 1\\
x^{25} + x^{23} + x^{21} + x^{19} + x^9 + x^7 + x^5 + x^3 + 1\\
x^{26} + x^6 + x^2 + x^1 + 1\\
x^{26} + x^{19} + x^{16} + x^{15} + x^{14} + x^{13} + x^{11} + x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + x^2 + 1\\
x^{26} + x^{21} + x^{18} + x^{16} + x^{15} + x^{13} + x^{12} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1\\
x^{26} + x^{22} + x^{20} + x^{19} + x^{16} + x^{13} + x^{11} + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1\\
x^{26} + x^{22} + x^{21} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^5 + x^4 + x^3 + x^1 + 1\\
x^{26} + x^{23} + x^{22} + x^{21} + x^{19} + x^{18} + x^{15} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^2 + 1\\
x^{26} + x^{24} + x^{21} + x^{17} + x^{16} + x^{14} + x^{13} + x^{11} + x^7 + x^6 + x^4 + x^1 + 1
x^{27} + x^5 + x^2 + x^1 + 1\\
x^{27} + x^{18} + x^{11} + x^{10} + x^9 + x^5 + x^4 + x^3 + 1\\
x^{27} + x^{22} + x^{13} + x^{11} + x^6 + x^5 + x^4 + x^3 + 1\\
x^{27} + x^{22} + x^{17} + x^{15} + x^{14} + x^{13} + x^6 + x^1 + 1\\
x^{27} + x^{22} + x^{21} + x^{20} + x^{18} + x^{17} + x^{15} + x^{13} + x^{12} + x^7 + x^5 + 1\\
x^{27} + x^{24} + x^{19} + x^{16} + x^{12} + x^8 + x^7 + x^3 + x^2 + x^1 + 1\\
x^{27} + x^{24} + x^{21} + x^{19} + x^{16} + x^{13} + x^{11} + x^9 + x^6 + x^5 + x^4 + x^3 + 1\\
x^{27} + x^{25} + x^{23} + x^{21} + x^{13} + x^{11} + x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{27} + x^{25} + x^{23} + x^{21} + x^{20} + x^{19} + x^{18} + x^{16} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1\\
x^{28} + x^3 + 1\\
x^{28} + x^{13} + x^{11} + x^9 + x^5 + x^3 + 1\\
x^{28} + x^{18} + x^{17} + x^{16} + x^9 + x^5 + x^4 + x^3 + 1\\
x^{28} + x^{19} + x^{17} + x^{15} + x^{10} + x^6 + x^3 + x^2 + 1\\
x^{28} + x^{22} + x^{11} + x^{10} + x^4 + x^3 + 1\\
x^{28} + x^{24} + x^{20} + x^{16} + x^{12} + x^8 + x^4 + x^3 + 1\\
x^{29} + x^2 + 1\\
x^{29} + x^{12} + x^7 + x^2 + 1\\
x^{29} + x^{18} + x^{14} + x^6 + x^3 + x^2 + 1\\
x^{29} + x^{19} + x^{16} + x^6 + x^3 + x^2 + 1\\
x^{29} + x^{20} + x^{11} + x^2 + 1\\
x^{29} + x^{20} + x^{16} + x^{11} + x^8 + x^4 + x^3 + x^2 + 1\\
x^{29} + x^{21} + x^5 + x^2 + 1\\
x^{29} + x^{23} + x^{10} + x^9 + x^5 + x^4 + x^3 + x^2 + 1\\
x^{29} + x^{24} + x^{14} + x^{13} + x^8 + x^4 + x^3 + x^2 + 1\\
x^{29} + x^{26} + x^5 + x^2 + 1\\
x^{30} + x^{23} + x^2 + x^1 + 1\\
x^{30} + x^{24} + x^{20} + x^{16} + x^{14} + x^{13} + x^{11} + x^7 + x^2 + x^1 + 1\\
x^{30} + x^{24} + x^{21} + x^{20} + x^{18} + x^{15} + x^{13} + x^{12} + x^9 + x^7 + x^6 + x^4 + x^3 + x^1 + 1\\
x^{30} + x^{25} + x^{24} + x^{23} + x^{19} + x^{18} + x^{16} + x^{14} + x^{11} + x^8 + x^6 + x^4 + x^3 + x^1 + 1\\
x^{30} + x^{27} + x^{25} + x^{24} + x^{23} + x^{22} + x^{19} + x^{16} + x^{12} + x^{10} + x^8 + x^7 + x^6 + x^1 + 1\\
x^{31} + x^3 + 1\\
x^{31} + x^3 + x^2 + x^1 + 1\\
x^{31} + x^{13} + x^8 + x^3 + 1\\
x^{31} + x^{16} + x^8 + x^4 + x^3 + x^2 + 1\\
x^{31} + x^{20} + x^{15} + x^5 + x^4 + x^3 + 1\\
x^{31} + x^{20} + x^{18} + x^7 + x^5 + x^3 + 1\\
x^{31} + x^{21} + x^{12} + x^3 + x^2 + x^1 + 1\\
x^{31} + x^{23} + x^{22} + x^{15} + x^{14} + x^7 + x^4 + x^3 + 1\\
x^{31} + x^{25} + x^{19} + x^{14} + x^7 + x^3 + x^2 + x^1 + 1\\
x^{31} + x^{27} + x^{23} + x^{19} + x^{15} + x^{11} + x^7 + x^3 + 1\\
x^{31} + x^{27} + x^{23} + x^{19} + x^{15} + x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 + x^2 + x^1 + 1\\
x^{32} + x^{22} + x^2 + x^1 + 1\\
x^{32} + x^{22} + x^{21} + x^{20} + x^{18} + x^{17} + x^{15} + x^{13} + x^{12} + x^{10} + x^8 + x^6 + x^4 + x^1 + 1\\
x^{32} + x^{23} + x^{17} + x^{16} + x^{14} + x^{10} + x^8 + x^7 + x^6 + x^5 + x^3 + 1\\
x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1\\
x^{32} + x^{27} + x^{26} + x^{25} + x^{24} + x^{23} + x^{22} + x^{17} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^2 + x^1 + 1\\
x^{32} + x^{28} + x^{19} + x^{18} + x^{16} + x^{14} + x^{11} + x^{10} + x^9 + x^6 + x^5 + x^1 + 1
$

\section{One way function}
Informally, a function f is a one-way function if
\\
1. The description of f is publicly known and does not require any secret information for its operation.\\
2. Given x, it is easy to compute f(x).\\
3. Given y, in the range of f, it is hard to find an x such that f(x)=y. More precisely, any efficient algorithm solving a P-problem succeeds in inverting f with negligible probability.
\par

The existence of one-way functions is not proven. If true, it would imply P!=NP. Therefore, it would answer the complexity theory NP-problem question of whether all apparently NP-problems are actually P-problems. Yet a number of conjectured one-way functions are routinely used in commerce and industry. For example, it is conjectured, but not proved, that the following are one-way functions:
\\
1. Factoring problem: f(p,q)=pq, for randomly chosen primes p,q.\\
2. Discrete logarithm problem:\\
\[f(p,g,x)=(p,g,g^x \pmod(p))\]
for g a generator of $Z_p^*$ for some prime p.\\
3. Discrete root extraction problem:$f(p,q,e,y)=(p,q,e,y^e \pmod(pq))$ , for y in $Z_{pq}^*$, e in $Z_{pq}$ and relatively prime to (p-1)(q-1), and p,q primes. This is the function commonly known as RSA encryption.\\

4. Subset sum problem: $f(a,b)=<\sum_{i=1}^{n}a_ib_i,b>$, for $a_i \in {0,1}$, and n-bit integers $b_i$.\\

5. Quadratic residue problem.\\

REFERENCES:\\
Luby, M. Pseudorandomness and Cryptographic Applications. Princeton, NJ: Princeton University Press, 1996.\\
Ziv, J. "In Search of a One-Way Function" 4.1 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 104-105, 1987.\\
FROM: \url{https://mathworld.wolfram.com/One-WayFunction.html}

\section{enigma}
在密码学史中，恩尼格玛密码机（见图\ref{enigmapic}）（德语：Enigma，又译哑谜机，或“谜”式密码机）是一种用于加密与解密文件的密码机。确切地说，恩尼格玛是对二战时期纳粹德国使用的一系列相似的转子机械加解密机器的统称，它包括了许多不同的型号，为密码学对称加密算法的流加密。\par
参考网站https://www.public-enigma.com/,这个网站上有enigma密码机的模拟程序Enigma Sim。\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{Enigma.png}
	\caption{德国海军使用的恩尼格码（Enigma）机器}
	\label{enigmapic}
\end{figure}

\section{Dan Boneh,Cryptography I}
Dan Boneh是Stanford大学的教授，他共享了一个六周的密码学基础的课程：
\url{https://www.coursera.org/learn/crypto/supplement/DGhhJ/lecture-slides-for-all-six-weeks}。

\section{各种安全模型}
安全模型有很多种，不同模型有不同的作用范围，不同的安全目标，不同的视角。
\subsection{Bell-LaPadula model}
Bell-Lapadula模型简称为BLP模型，是一种强制访问控制（MAC:Mandatory Access Control）模型。下面是WIKI\footnote{https://encyclopedia.thefreedictionary.com/Bell-LaPadula+model ,此网站是wiki的一个镜像。}关于此模型的介绍。\par

The Bell–LaPadula Model (BLP) is a state machine model used for enforcing access control in government and military applications.[1] It was developed by David Elliott Bell [2] and Leonard J. LaPadula, subsequent to strong guidance from Roger R. Schell to formalize the U.S. Department of Defense (DoD) multilevel security (MLS) policy.[3][4][5] The model is a formal state transition model of computer security policy that describes a set of access control rules which use security labels on objects and clearances for subjects. Security labels range from the most sensitive (e.g., "Top Secret"), down to the least sensitive (e.g., "Unclassified" or "Public").\par
The Bell–LaPadula model is an example of a model where there is no clear distinction of protection and security.[6]\par

\textbf{Features}

The Bell–LaPadula model focuses on data confidentiality and controlled access to classified information, in contrast to the Biba Integrity Model which describes rules for the protection of data integrity. In this formal model, the entities in an information system are divided into subjects and objects. The notion of a "secure state" is defined, and it is proven that each state transition preserves security by moving from secure state to secure state, thereby inductively proving that the system satisfies the security objectives of the model. The Bell–LaPadula model is built on the concept of a state machine with a set of allowable states in a computer system. The transition from one state to another state is defined by transition functions.\par
A system state is defined to be "secure" if the only permitted access modes of subjects to objects are in accordance with a security policy. To determine whether a specific access mode is allowed, the clearance of a subject is compared to the classification of the object (more precisely, to the combination of classification and set of compartments, making up the security level) to determine if the subject is authorized for the specific access mode. The clearance/classification scheme is expressed in terms of a lattice. The model defines two mandatory access control (MAC) rules and one discretionary access control (DAC) rule with three security properties:\par
The Simple Security Property - a subject at a given security level may not read an object at a higher security level.\par
The *-property (read "star"-property) - a subject at a given security level must not write to any object at a lower security level, and not read any object at a higher security level.\par
The Discretionary Security Property - use of an access matrix to specify the discretionary access control.\par
The transfer of information from a high-sensitivity document to a lower-sensitivity document may happen in the Bell–LaPadula model via the concept of trusted subjects. Trusted Subjects are not restricted by the Star-property. Trusted Subjects must be shown to be trustworthy with regard to the security policy. This security model is directed toward access control and is characterized by the phrase: "no read up, no write down." Compare the Biba model, the Clark-Wilson model and the Chinese Wall model.\par
With Bell-LaPadula, users can create content only at or above their own security level (i.e. secret researchers can create secret or top-secret files but may not create public files; no write-down). Conversely, users can view content only at or below their own security level (i.e. secret researchers can view public or secret files, but may not view top-secret files; no read-up).\par
The Bell–LaPadula model explicitly defined its scope. It did not treat the following extensively:\par
Covert channels. Passing information via pre-arranged actions was described briefly.
Networks of systems. Later modeling work did address this topic.\par
Policies outside multilevel security. Work in the early 1990s showed that MLS is one version of boolean policies, as are all other published policies.\par
\textbf{Strong Star Property}
The Strong Star Property is an alternative to the *-Property, in which subjects may write to objects with only a matching security level. Thus, the write-up operation permitted in the usual *-Property is not present, only a write-to-same operation. The Strong Star Property is usually discussed in the context of multilevel database management systems and is motivated by integrity concerns.[7] This Strong Star Property was anticipated in the Biba model where it was shown that strong integrity in combination with the Bell–LaPadula model resulted in reading and writing at a single level.\par
\textbf{Tranquility principle}
The tranquility principle of the Bell–LaPadula model states that the classification of a subject or object does not change while it is being referenced. There are two forms to the tranquility principle: the "principle of strong tranquility" states that security levels do not change during the normal operation of the system. The "principle of weak tranquility" states that security levels may never change in such a way as to violate a defined security policy. Weak tranquility is desirable as it allows systems to observe the principle of least privilege. That is, processes start with a low clearance level regardless of their owners clearance, and progressively accumulate higher clearance levels as actions require it.\par
\textbf{Limitations}

Only addresses confidentiality, control of writing (one form of integrity), *-property and discretionary access control
Covert channels are mentioned but are not addressed comprehensively
The tranquility principle limits its applicability to systems where security levels do not change dynamically. It allows controlled copying from high to low via trusted subjects.
The state-transition model does not contain any state invariants.
The overall process may take more time.

\subsection{ISO安全模型}
本节内容来源于开源电子书\footnote{内容来源于开源电子书，\url{https://tumregels.github.io/Network-Programming-with-Go/security/iso_security_architecture.html}}，本部分内容在中文参考书\cite{feng-cs}也有详尽描述。\par
ISO security architecture\par
The ISO OSI (open systems interconnect) seven-layer model of distributed systems is well known and is repeated in this figure \ref{ISO-NSA}.\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{ISO-NSA.jpg}
	\caption{ISO安全架构}
	\label{ISO-NSA}
\end{figure}
What is less well known is that ISO built a whole series of documents upon this architecture. For our purposes here, the most important is the ISO Security Architecture model, ISO 7498-2.\par

\textbf{Functions and levels}

The principal functions required of a security system are：\par
\begin{itemize}
	\item Authentication - proof of identity
	\item Data integrity - data is not tampered with
	\item Confidentiality - data is not exposed to others
	\item Notarization/signature
	\item Access control
	\item Assurance/availability
\end{itemize}

These are required at the following levels of the OSI stack:\par
\begin{itemize}
	\item Peer entity authentication (3, 4, 7)
	\item Data origin authentication (3, 4, 7)
	\item Access control service (3, 4, 7)
	\item Connection confidentiality (1, 2, 3, 4, 6, 7)
	\item Connectionless confidentiality (1, 2, 3, 4, 6, 7)
	\item Selective field confidentiality (6, 7)
	\item Traffic flow confidentiality (1, 3, 7)
	\item Connection integrity with recovery (4, 7)
	\item Connection integrity without recovery (4, 7)
	\item Connection integrity selective field (7)
	\item Connectionless integrity selective field (7)
	\item Non-repudiation at origin (7)
	\item Non-repudiation of receipt (7)
\end{itemize}

\textbf{Mechanisms}
\begin{itemize}
	\item Peer entity authentication
	\begin{itemize}
		\item encryption
		\item digital signature
		\item authentication exchange
	\end{itemize}
	
	\item Data origin authentication
		\begin{itemize}
			\item encryption
			\item digital signature
		\end{itemize}
		
		
	\item Access control service
		\begin{itemize}
			\item access control lists
			\item passwords
			\item capabilities lists
			\item labels
		\end{itemize}
		
		
	\item Connection confidentiality
		\begin{itemize}
			\item encryption
			\item routing control
		\end{itemize}
		
		
	\item Connectionless confidentiality
		\begin{itemize}
			\item encryption
			\item routing control
		\end{itemize}
		
		
	\item Selective field confidentiality
		\begin{itemize}
			\item encryption
		\end{itemize}
		
		
	\item Traffic flow confidentiality
		\begin{itemize}
			\item encryption
			\item traffic padding
			\item routing control
		\end{itemize}
		
		
	\item Connection integrity with recovery
		\begin{itemize}
			\item encryption
			\item data integrity
		\end{itemize}
		
		
	\item Connection integrity without recovery
		\begin{itemize}
			\item encryption
			\item data integrity
		\end{itemize}
		
		
	\item Connection integrity selective field
		\begin{itemize}
			\item encryption
			\item data integrity
		\end{itemize}
		
		
	\item Connectionless integrity
		\begin{itemize}
			\item encryption
			\item digital signature
			\item data integrity
		\end{itemize}
		
		
	\item Connectionless integrity selective field
		\begin{itemize}
			\item encryption
			\item digital signature
			\item data integrity
		\end{itemize}
		
		
	\item Non-repudiation at origin
		\begin{itemize}
			\item digital signature
			\item data integrity
			\item notarization
		\end{itemize}
		
		
	\item Non-repudiation of receipt
		\begin{itemize}
			\item digital signature
			\item data integrity
			\item notarization
		\end{itemize}
		
\end{itemize}

\subsection{IATF安全模型(ISSE)}

\subsection{BS7799 PDCA模型}

\section{课程设计基本概念}
本部分内容主要参考自“Curriculum Design：Definition，Purpose and types”\footnote{https://www.thoughtco.com/for-educators-4132509}。\par
课程设计（curriculum design）是一个用来描述在一节课或者一个课程中，有目的、有意地和系统地组织（purposeful,deliberate and systematic organization）教学模块（instructional blocks）,换句话来说，是教师教学计划（plan instruction）的一种方式。教师在设计课程时必须明确“做什么、谁做、日程安排”（whar will be done,who will do it,and what schedule to follow）.
\subsection{课程设计的目的}
课程设计的终极目标是改善学生的学习（improve student learning)。教师在课程设计时，脑中一定要个一个明确的教育目的（specific educational purpose in mind）。在课程设计时也要特别注意学习目标在不同阶段的衔接和互补（learning goals are aligned and complement each other from on stage to the next）。
\subsection{课程设计的类型}
\subsubsection{学科为中心的课程设计(subject-centered curriculum design)}
学科为中心的课程设计围绕一个特定的学科材料或者准则，需要描述“需要学什么和怎么学”，通常教师会给出一个需要交给学生的知识点表，同时附上一个例子来说说明如何交给学生，目前绝大多数课程设计都是采用这种方式。这种方式不是以学生为中心，课程设计时没有考虑学生的学习方式，学生的主动性和积极性会是一个问题。
\subsubsection{学习者为中心的课程设计(learner-centered curriculum design)}
学习者为中心的方法考虑到每个学习者的需要、兴趣和目标（each individual's needs,interests, and goals)，这种方法承认学生的不一致性，根据学生的需要来调整，这意味着赋能学习者（empower learners），同时也允许学习者通过选择来重塑他们的教育（shape their education through choices）.\par
以学习者为中心的教学方案(instructional plans)给学生选择作业、学习体验或者活动的机会，这可以调动学生，帮助他们在他们学习的内容上投入更多(help them stay engaged in the material that they are learning).\par
这种方法的缺点是劳动密集型（labor-intensive),开发有区别的指导（developing differentiated instruction）对老师是个巨大压力，需要老师开发出不同的指导，针对每个学生的需求找到其所需的引导材料，在这种情况下，老师的时间、经验、技巧都要有足够的保障和支持，同时也要求老师在学生的需要、课程所需的输出之间寻找平衡，这也是一个巨大的挑战。
\subsubsection{问题为中心的课程设计(problem-centered curriculum design)}
问题为中心的课程设计也是一种学生为中心的形式，问题为中心的课程设计聚焦在“学生如何开一个问题和如何找到解决问题的方案”，问题为中心的课程设计增加了课程之间的相关性，允许学生在学习时更具创造性和创新性，缺点是并不总是考虑到学习的方式（does not always take learning styles into consideration).

\subsubsection{课程设计时的几点注意事项}
\begin{itemize}
	\item 搞清学生需求,可对学生的需求进行分析保留收集分析学习者的相关数据，比如学习者在某些领域或者相关技能已经知道的、需要知道的，也可以包括学习者的认知、优缺点（perception，strengths and weaknessed).
	\item 建立一个清晰的学习目标（learning goals）和产出（learning outcomes）列表，学习目标是老师想让学生在课程中达到的结果，学习产出是学生在课程学习后应该达到的、可检测的知识、技能和态度（measurable knowledge,skills, and attitudes that students should have achieved in the course）
	\item 搞清限制条件，要明确影响课程设计的因素，比如课程时间等。
	\item 考虑建立一个课程地图，通常也称为课程矩阵。
	\item 明确教学方法，教学方法应该考虑如何和学生的学生类型共同起作用，如果教学方法无益于课程，就需要进行更换。
	\item 建立不同的评估方法，在过程结束或者过程中需要评估学习者、教师和课程，评估帮助你确定课程设计是否起作用或者没有，还有就是评估课程输出的达成度，最有效的评估是持续的和累计的（ongoing and summative）。
	\item 谨记课程设计不是一蹴而就，需要持续改进。
\end{itemize}

\section{The Vernam Cipher}
Vernam是AT\&T公司设计的一次一密系统，下面图\ref{vernam-intro}是\url{https://cryptomuseum.com/crypto/vernam.htm}关于Vernam密码机的资料。\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{Vernam.pdf}
	\caption{Vernam密码机介绍}
	\label{vernam-intro}
\end{figure}

\section{工具RSA-Tool 2中的公私钥生成方法}
RSA Tool 2是互联网上一个广为流程的RSA工具，界面如\ref{RSA-Tool-2}。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{RSA-Tool-2.png}
	\caption{RSA Tool 2生成公私钥的界面}
	\label{RSA-Tool-2}
\end{figure}
其在软件说明中，对于密钥生成的描述如下：\par
2. Parameters \par
P = 1st large prime number\par
Q =  2nd large prime number  (sizes of P and Q should not differ too much!)\par
E = Public  Exponent (a random number  which must fulfil:\par
GCD(E,  (P-1)*(Q-1))==1)\par
N = Public Modulus, the product of P and Q: N=P*Q\par
D = Private Exponent: $D=E^(-1) mod ((P-1)*(Q-1))$\par

Parameters N  and E are  public whereas D  is -private- and  must NEVER be
published! P and Q are not longer needed after keygeneration and should be
destroyed.\par

To obtain D from the public key (N, E) one needs to try splitting N in its
both prime factors P and Q. For a large Modulus N  (512 bit and more) with
carefully chosen primefactors P and Q this is a very difficult problem.\par

All the security  of the RSA encryption scheme relies on that integer
factorization problem (tough there's no mathematical proof for it).
To find out more read here:\par
\url{http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html}
\par

3. Encryption\par
To encrypt a messageblock (M) (which must be < N), compute:\par
Ciphertext = $C = M^E mod N$.\par
Note:  If the  entire message  (M) is  > N  it must  be split into smaller
blocks with size < N\par

4. Decryption\par
To decrypt a given Ciphertext (C) to retrieve the Plaintext (M) as result,
compute: $M=C^D mod N$.\par

The ' \^ ' sign in the above equations means 'power of', not XOR !\par

Note that the RSA scheme does also work the other way round:\par
$C=M^D mod N$ and $M=C^E mod N$. It's on you how you implement it. Just ALWAYS
make SURE that you -NEVER- publish the private exponent D, P and//or Q !\par

5. How to ...?\par
...Generate a RSA keypair ?\par
1) Press the 'Start' Button to collect some (pseudo) random data by moving
around your mousepointer.\par
This must  be done only  one time, because  the collected data  will be
saved in a file in your RSA-Tool folder.\par
2) Select the number base you want  to use for your keys. Base 10, 16,  60
and 64 are available.\par
3) Select the  size of of the  key (=size of N)  you want to create.  Max.
keysize is 4096 bit.\par
4) Choose  your public  exponent (E)  and type  it in  the corresponding
Editbox as DECIMAL number.
Most common values (calculation-speed  reasons) used for E are:
3, 17, 257 and 65537 (decimal)
5) Press the  Generate  button and  wait  until keygeneration  has  been
finished.
Note that generation of very  large keys can take some time,  depending
on the power of your CPU.\par
Important: You can  press Generate as often  as you like. The  internal
random number  generation  system,  which is used in a part of the  key
generation process, will be re-initialized during runtime.\par
This is done on purpose, as it makes it much harder to abuse this  tool
for certain things...Note that this also  makes it  almost *impossible*
to create the same keypair twice or more.\par
It can happen  that your Modulus will  become e.g. 159 Bits  only, even
when you selected  160 Bits  as keysize.  The reason is the little size
difference between P and Q. If  you are not satisfied, simply press the
Generate button again until the desired keylength meets your needs :-)
\par